B. Substring and Subsequence
给你两个字符串
你的任务是计算使得
我的方法是三层循环的,如果数据严格一点肯定过不了的。
void solve() {
string a, b;cin >> a >> b;
int ans = 0;
for (int i = 0;i < a.size();i++) {
for (int j = 0;j < b.size();j++) {
if (a[i] == b[j]) {
int p = i;int x = 0;
for (int k = j;k < b.size() && p < a.size();p++) {
if (a[p] == b[k]) {
x++;k++;
}
}
ans = max(ans, x);
}
}
}
cout << a.size() + b.size() - ans << '\n';
}
官方题解:两层循环:
void solve() {
string a, b;cin >> a >> b;
size_t ans = a.size() + b.size();
for (int i = 0; i < b.size(); ++i) {
int j = i;
for (auto c : a) {
if (j < b.size() && c == b[j]) ++j;
}
ans = min(ans, a.size() + b.size() - (j - i));
}
cout << ans << '\n';
}